from random import randint


class Skiplist:
    class _Node:
        def __init__(self, val):
            self.val = val
            self.right = None
            self.down = None

    def __init__(self):
        self.start = [self._Node(-1) for _ in range(16)]
        self.end = [self._Node(20001) for _ in range(16)]
        for i in range(16):
            self.start[i].right = self.end[i]
        for i in range(15):
            self.start[i].down = self.start[i + 1]

    def search(self, target: int) -> bool:
        node = self.start[0]
        while node:
            if node.right.val > target:
                node = node.down
            elif node.right.val < target:
                node = node.right
            else:
                return True
        return False

    def add(self, num: int) -> None:
        node = self.start[0]
        stack = []
        while node:
            if node.right.val >= num:
                stack.append(node)
                node = node.down
            else:
                node = node.right

        down = None
        while stack:
            left = stack.pop()
            node = self._Node(num)
            node.right = left.right
            left.right = node
            node.down = down
            down = node
            if randint(0, 1) == 1:
                break

    def erase(self, num: int) -> bool:
        node = self.start[0]
        already_remove = False
        while node:
            if node.right.val > num:
                node = node.down
            elif node.right.val < num:
                node = node.right
            else:
                already_remove = True
                node.right = node.right.right
                node = node.down
        return already_remove


if __name__ == "__main__":
    obj = Skiplist()
    obj.add(1)
    obj.add(2)
    obj.add(3)
    print(obj.search(0))  # False
    obj.add(4)
    print(obj.search(1))  # True
    print(obj.erase(0))  # False
    print(obj.erase(1))  # True
    print(obj.search(1))  # False
